#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
#include<map>
#include<set>
using namespace std;


//暴力解法
// class Solution {
// public:
//     vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
//         sort(A.begin(),A.end());
//         sort(B.begin(),B.end());
//         for(int i = 0;i<A.size();++i){
//             for(int j = B.size()-1;j>=0;--j){
//                 int temp = A[i];
//                 A[i] = B[j];
//                 B[j] = temp;
//                 if(accumulate(A.begin(),A.end(),0)==accumulate(B.begin(),B.end(),0)){
//                     return {B[j],A[i]};
//                 }
//                 else{
//                     B[j] = A[i];
//                     A[i] = temp;
//                 }
//             }
//         }
//         return {};

//     }
// };

//非暴力解法
class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumA = accumulate(A.begin(),A.end(),0);
        int sumB = accumulate(B.begin(),B.end(),0);
        for(int i = 0;i<A.size();++i){
            int y = A[i]+(sumB-sumA)/2;
            if(find(B.begin(),B.end(),y)!=B.end()){
                return {A[i],y};
            }
        }
        return {};
    }
};

int main(){
    Solution S;
    vector<int> A = {35,17,4,24,10};
    vector<int> B = {63,21};
    vector<int> result = S.fairCandySwap(A,B);
    return 0;
}